//
// Created by zhou on 2021/10/30.
//

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
class Solution {
public:
    int compare(int i,int j,int k){
        int x=pow(2,i);
        int y=pow(3,j);
        int z=pow(5,k);
        int max_=0;
        max_=max(x,y);
        max_=max(max_,z);
        if(max_==x)return 0;
        else if(max_==y)return 1;
        else return 2;
    }
    int nthUglyNumber(int n) {
        int i=0,j=0,k=0;
        int dp[n];
        dp[0]=1;
        if(n==1)return dp[0];
        for(int m=1;m<n;m++){
            if(i==0&&j==0&&k==0){
                dp[m]=2;
                i+=1;
                continue;
            }
            int compare_= compare(i,j,k);
            if(compare_==0){
                i-=1;
                j+=1;
            }
            else if(compare_==1){
                i+=2;
                j-=1;
            }
            else if(compare_==2){
                k-=1;
                i+=1;
                j+=1;
            }
            dp[m]=pow(2,i)*pow(3,j)*pow(5,k);
        }
        return dp[n-1];
    }
};
int main(){
    Solution solution;
    cout<<solution.nthUglyNumber(3);
}